In this note is proved the following:Theorem.Iƒ A × B is universal and one oƒ A, B is r.e. then one of A, B is universal.Letα, τbe 1-argument recursive functions such thatxgoes to, τ) is a map of the natural numbers onto all ordered pairs of natural numbers. A set A of natural numbers is calleduniversalif every r.e. set is reducible to A; A × B is calleduniversalif the set.

Let T be a complete first-order theory over a finite relational language which is axiomatized by universal and existential sentences. It is shown that T is almost trivial in the sense that the universe of any model of T can be written $F \overset{\cdot}{\cup} I_1 \overset{\cdot}{\cup} I_2 \overset{\cdot}{\cup} \cdots \overset{\cdot}{\cup} I_n$ , where F is finite and I 1 , I 2 ,...,I n are mutually indiscernible over F. Some results about complete theories with ∃∀-axioms over a finite relational language (...) are also mentioned. (shrink)

Our purpose in this note is to study countable ℵ0-categorical structures whose theories are tree-decomposable in the sense of Baldwin and Shelah. The permutation group corresponding to such a structure can be decomposed in a canonical manner into simpler permutation groups in the same class. As an application of the analysis we show that these structures are finitely homogeneous.

LetT be a universal theory of graphs such that Mod(T) is closed under disjoint unions. Letℳ T be a disjoint union ℳ i such that eachℳ i is a finite model ofT and every finite isomorphism type in Mod(T) is represented in{ℳ i ∶i<Ω3}. We investigate under what conditions onT, Th(ℳ T ) is a coinductive theory, where a theory is called coinductive if it can be axiomatizated by ∃∀-sentences. We also characterize coinductive graphs which have quantifier-free rank 1.

Sacks [2] has asked whether there exists a uniform solution to Post's problem, i.e. an enumeration operation W such that $\mathbf{d} for every degree d. It is shown here that if such an operation W exists it cannot itself in a particular technical sense be uniform. In fact, the jump operation is characterized amongst such uniform enumeration operations by the condition: $\mathbf{d} for all d. In addition, it is proved that the only other uniform enumeration operations such that d ≤ (...) W (d) for all d are those which equal the identity operation above some fixed degrees. (shrink)